package java_calculation;

import java.util.ArrayList;

/***
 * 链表判断用方法
 */
public class demo_01_linked_check {
    public static void main(String[] arge){
        // ------------------------------------------------------------------------
        /**
         * 判断一：判断是否是循环链表
         */
        // 创建测试用链表A
        // 0001->0002->0003-> .... ->9999->0001
        Node_linked_check node_A_01  = new Node_linked_check("0001");
        Node_linked_check nodeTemp = node_A_01;
        for(int i = 2;i<=9999;i++){
            Node_linked_check newNode = new Node_linked_check(String.format("%04d", i));
            nodeTemp.setNext(newNode);
            nodeTemp = newNode;
        }
        nodeTemp.setNext(node_A_01);

        // 方法一：循环判断
        long test_time_01 = System.nanoTime();
        boolean test_bol_01 = false;
        ArrayList<String> test_key_01 = new ArrayList<String>(1000);
        Node_linked_check test_01_node = node_A_01;
        while (test_01_node.getNext() != null){
            if(test_key_01.indexOf(test_01_node.getKey()) != -1){
                test_bol_01 = true;
                break;
            }
            test_key_01.add(test_01_node.getKey());
            test_01_node = test_01_node.getNext();
        }
        System.out.println("test1判断完成，是否循环："+test_bol_01+",用时："+(System.nanoTime()-test_time_01));


        // 方法二：指针循环
        // 双向指针循环
        //  0001 ->   0002 ->   0003 ->   0004 ....
        //   |        |
        // node_01   node_02
        // 不断判断指针指向两对象是否相同
        // 使用追逐法：指针变化方法为node_01每次移动1，node_02每次移动2
        long test_time_02 = System.nanoTime();
        boolean test_bol_02 = false;
        Node_linked_check test_02_node_01 = node_A_01;
        Node_linked_check test_02_node_02 = node_A_01;
        while ((test_02_node_01.getNext() != null) && (test_02_node_02.getNext() != null) && (test_02_node_02.getNext().getNext() != null)){
            if(test_02_node_01 == test_02_node_02){
                test_bol_02 = true;
                break;
            }

            test_02_node_01 = test_02_node_01.getNext();
            test_02_node_02 = test_02_node_02.getNext().getNext();
        }
        System.out.println("test2判断完成，是否循环："+test_bol_02+",用时："+(System.nanoTime()-test_time_02));
        // ------------------------------------------------------------------------
        /**
         * 判断二：依旧是一的链表，判断入环点
         */
        // 方法一：循环判断
        long test_time_03 = System.nanoTime();
        Node_linked_check node_same = null;
        ArrayList<String> test_key_03 = new ArrayList<String>(1000);
        Node_linked_check test_03_node = node_A_01;
        while (test_03_node.getNext() != null){
            if(test_key_03.indexOf(test_03_node.getKey()) != -1){
                node_same = test_03_node;
                break;
            }
            test_key_03.add(test_03_node.getKey());
            test_03_node = test_03_node.getNext();
        }
        System.out.println("test3判断完成，循环点："+node_same.getKey()+",用时："+(System.nanoTime()-test_time_03));

        // 方法二：指针循环
        // 计算节点数，node_01走X，node_02走2X后相遇，环长度为N的话，因为则2X = X + RN，所以X = RN(不知道到相遇为止走了几圈)
        // Y为开头到节点的距离的话，2X - Y = X - Y + RN
        // 此时，如果上述公式，再走Y步的话变成2X = X + RN，其实就是第二次相遇。所以，第二次相遇点，一定为入口
        long test_time_04 = System.nanoTime();
        int test_int_04 = 0;
        Node_linked_check node_same_04 = null;
        Node_linked_check test_04_node_01 = node_A_01;
        Node_linked_check test_04_node_04 = node_A_01;
        while ((test_04_node_01.getNext() != null) && (test_04_node_04.getNext() != null) && (test_04_node_04.getNext().getNext() != null)){
            if(test_04_node_01 == test_04_node_04){
                test_int_04 ++;
                if(test_int_04 == 2){
                    node_same_04 = test_04_node_01;
                    break;
                }
            }

            test_04_node_01 = test_04_node_01.getNext();
            test_04_node_04 = test_04_node_04.getNext().getNext();
        }
        System.out.println("test4判断完成，循环点："+node_same_04.getKey()+",用时："+(System.nanoTime()-test_time_04));

    }
}



// 测试用节点
class Node_linked_check {
    private final String key;
    private Node_linked_check next;
    Node_linked_check(String key) {
        this.key = key;
    }
    public String getKey() {
        return key;
    }
    public Node_linked_check getNext() {
        return next;
    }
    public void setNext(Node_linked_check next) {
        this.next = next;
    }
}
